//628. 三个数的最大乘积
//思路：此题的本质是找出最小的两个数字与最大的三个数字出来
//最小的两个相乘再与最大的相乘，比较最大的三个相乘，找出两个乘积最大的返回

#include <stdlib.h>
#include <math.h>
//法一：排序，时间复杂度：O(n*log n)，空间复杂度：O(n)，排序时消耗
// int cmp_int(const void* p1, const void* p2){
//     return *(int*)p1 - *(int*)p2;
// }
// int maximumProduct(int* nums, int numsSize){
//     qsort(nums, numsSize, sizeof(int), cmp_int);
//     return fmax(nums[0]*nums[1]*nums[numsSize-1],
//             nums[numsSize-1]*nums[numsSize-2]*nums[numsSize-3]);    
// }


//法二：线性查找，时间复杂度：O(n),空间复杂度：O(1)
int maximumProduct(int* nums, int numsSize){
    int min1 = INT_MAX, min2 = INT_MAX;
    int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
    for(int i = 0; i < numsSize; i++)
    {
        int x = nums[i];
        if(x < min1)
        {
            min2 = min1;
            min1 = x;
        }
        else if(x < min2)
        {
            min2 = x;
        }

        if(x > max1)
        {
            max3 = max2;
            max2 = max1;
            max1 = x;
        }
        else if(x > max2)
        {
            max3 = max2;
            max2 = x;
        }
        else if(x > max3)
        {
            max3 = x;
        }
    }
    return fmax(min1*min2*max1, max1*max2*max3);
}
